#!/usr/bin/env python
# -*- coding: utf-8 -*-

import networkx as nx
import matplotlib.pyplot as plt

def drawNFA(Input):
    labels = {}
    transMap = Input.transferTable
    G = nx.Graph()
    for i in range(len(Input.states)):
        G.add_node(i)
        labels[i] = i
    for i in range(1, len(Input.states)+1):
        for j in range(1, len(transMap[0])):
            if transMap[i][j] != '∅':
                if type(transMap[i][j]) == int:
                    G.add_weighted_edges_from([(transMap[i][0], transMap[i][j], transMap[0][j])])
    edge_labels = nx.get_edge_attributes(G, 'weight')
    pos=nx.circular_layout(G)
    print pos
    nx.draw_networkx_nodes(G, pos, node_color='g', node_size=500, alpha=0.8)
    nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5, edge_color='b')
    nx.draw_networkx_labels(G, pos, labels, font_size=16)
    nx.draw_networkx_edge_labels(G, pos, edge_labels)
    plt.draw()
    plt.show()

class NFA:

    def __init__(self, infix, type=1):
        # 0: simplest init 1: wait to be combined
        self.infix = infix
        self.states = []
        self.transferTable = []
        if type == 0:
            self.states += [0]
            self.states += [100]
            self.transferTable += [['head', self.infix]]
            self.transferTable += [[0, 100]]
            self.transferTable += [[100, '∅']]

    def seriesConnection(self, InputNFA):
        Amark = []
        Bmark = []
        for value in self.states:
            if value != 100:
                Amark += [value]
        for value in InputNFA.states:
            if value != 100:
                Bmark += [value+len(self.states)-1]
        Bmark += [100]
        result = NFA(self.infix + InputNFA.infix, 1)
        result.states = Amark + Bmark
        head = list(set(self.transferTable[0]).union(set(InputNFA.transferTable[0])))
        headIndex = head.index('head')
        if headIndex != 0:
            head[headIndex] = head[0]
            head[0] = 'head'
        if 'ε' in head:
            eIndex = head.index('ε')
            if eIndex != len(head) - 1:
                head[eIndex] = head[len(head)-1]
                head[len(head)-1] = 'ε'
        result.transferTable = [['∅' for i in range(0, len(head))] for j in range(0, len(result.states)+1)]
        result.transferTable[0] = head
        aMark = []
        bMark = []
        for i in range(1, len(result.states)+1):
            result.transferTable[i][0] = result.states[i-1]
        for ch in self.transferTable[0][1:]:
            if ch in result.transferTable[0]:
                aMark += [result.transferTable[0].index(ch)]
        for ch in InputNFA.transferTable[0][1:]:
            if ch in result.transferTable[0]:
                bMark += [result.transferTable[0].index(ch)]
        for j in range(len(aMark)):
            result.transferTable[len(self.states)][aMark[j]] = self.transferTable[len(self.states)][j+1]
            for i in range(len(self.states)-1):
                if type(self.transferTable[i+1][j+1]) == int:
                    if self.transferTable[i+1][j+1] != 100:
                        result.transferTable[i+1][aMark[j]] = self.transferTable[i+1][j+1]
                    else:
                        result.transferTable[i+1][aMark[j]] = len(self.states)-1
                elif type(self.transferTable[i+1][j+1]) == list:
                    if 100 not in self.transferTable[i+1][j+1]:
                        result.transferTable[i+1][aMark[j]] = self.transferTable[i+1][j+1]
                    else:
                        index = self.transferTable[i+1][j+1].index(100)
                        result.transferTable[i+1][aMark[j]] = self.transferTable[i+1][j+1]
                        result.transferTable[i+1][aMark[j]][index] = len(self.states)-1
        for j in range(len(bMark)):
            if type(InputNFA.transferTable[1][j+1]) == int:
                if InputNFA.transferTable[1][j+1] != '∅' and InputNFA.transferTable[1][j+1] != 100:
                    result.transferTable[len(self.states)][bMark[j]] = InputNFA.transferTable[1][j+1] + len(self.states) - 1
                else:
                    result.transferTable[len(self.states)][bMark[j]] = InputNFA.transferTable[1][j+1]
            elif type(InputNFA.transferTable[1][j+1]) == list:
                result.transferTable[len(self.states)][bMark[j]] = InputNFA.transferTable[1][j+1]
                for i in range(len(result.transferTable[len(self.states)][bMark[j]])):
                    if result.transferTable[len(self.states)][bMark[j]][i] != 100:
                        result.transferTable[len(self.states)][bMark[j]][i] += len(self.states) - 1
            for i in range(len(InputNFA.states)-1):
                if type(InputNFA.transferTable[i+2][j+1]) == int:
                    if InputNFA.transferTable[i+2][j+1] != '∅' and InputNFA.transferTable[i+2][j+1] != 100:
                        result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]] = InputNFA.transferTable[i+2][j+1] + len(self.states) - 1
                    else:
                        result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]] = InputNFA.transferTable[i+2][j+1]
                elif type(InputNFA.transferTable[i+2][j+1]) == list:
                    result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]] = InputNFA.transferTable[i+2][j+1]
                    for k in range(len(result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]])):
                        if result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]][k] != 100:
                            result.transferTable[len(result.transferTable)-len(InputNFA.states)+1+i][bMark[j]][k] += len(self.states) - 1
        return result

    def parallelConnection(self, InputNFA):
        aMark = []
        bMark = []
        result = NFA(self.infix + '|' + InputNFA.infix, 1)
        for i in range(len(self.states)-1):
            aMark += [i+1]
        aMark += [len(self.states)]
        for i in range(len(InputNFA.states)-1):
            bMark += [len(self.states)+i+1]
        bMark += [len(self.states) + len(InputNFA.states)]
        head = list(set(self.transferTable[0]).union(set(InputNFA.transferTable[0])).union(set(['ε'])))
        headIndex = head.index('head')
        if headIndex != 0:
            head[headIndex] = head[0]
            head[0] = 'head'
        eIndex = head.index('ε')
        if eIndex != len(head) - 1:
            head[eIndex] = head[len(head)-1]
            head[len(head)-1] = 'ε'
        result.states += [0] + aMark + bMark + [100]
        result.transferTable = [['∅' for i in range(len(head))] for j in range(len(result.states)+1)]
        result.transferTable[0] = head
        for i in range(1, len(result.states) + 1):
            result.transferTable[i][0] = result.states[i-1]
        for i in range(len(self.states)-1):
            for j in head:
                if j in self.transferTable[0] and j != 'head':
                    index1 = result.transferTable[0].index(j)
                    index2 = self.transferTable[0].index(j)
                    if self.transferTable[i+1][index2] != '∅':
                        if type(self.transferTable[i+1][index2]) == int:
                            result.transferTable[aMark[i]+1][index1] = aMark[self.states.index(self.transferTable[i+1][index2])]
                        elif type(self.transferTable[i+1][index2]) == list:
                            result.transferTable[aMark[i]+1][index1] = self.transferTable[i+1][index2]
                            for k in range(len(self.transferTable[i+1][index2])):
                                # print aMark[self.states.index(self.transferTable[i+1][index2][i])]
                                # print len(self.transferTable[i+1][index2])
                                # print aMark[self.states.index(self.transferTable[i+1][index2][i])]
                                result.transferTable[aMark[i]+1][index1][k] = aMark[self.states.index(self.transferTable[i+1][index2][k])]
        for i in range(len(InputNFA.states)-1):
            for j in head:
                if j in InputNFA.transferTable[0] and j != 'head':
                    index1 = result.transferTable[0].index(j)
                    index2 = InputNFA.transferTable[0].index(j)
                    if InputNFA.transferTable[i+1][index2] != '∅':
                        if type(InputNFA.transferTable[i+1][index2]) == int:
                            result.transferTable[bMark[i]+1][index1] = bMark[InputNFA.states.index(InputNFA.transferTable[i+1][index2])]
                        elif type(InputNFA.transferTable[i+1][index2]) == list:
                            result.transferTable[bMark[i]+1][index1] = InputNFA.transferTable[i+1][index2]
                            for k in range(len(InputNFA.transferTable[i+1][index2])):
                                result.transferTable[bMark[i]+1][index1][k] = bMark[InputNFA.states.index(InputNFA.transferTable[i+1][index2][k])]
        index = head.index('ε')
        result.transferTable[aMark[len(self.states)-1]+1][index] = 100
        result.transferTable[bMark[len(InputNFA.states)-1]+1][index] = 100
        result.transferTable[1][index] = [aMark[0], bMark[0]]
        return result

    def circuitConnection(self):
        aMark = []
        result = NFA(self.infix, 1)
        for i in range(len(self.states)-1):
            aMark += [i+1]
        aMark += [len(self.states)]
        result.states += [0] + aMark + [100]
        if 'ε' not in self.transferTable[0]:
            head = self.transferTable[0] + ['ε']
        else:
            head = self.transferTable[0]
        result.transferTable = [['∅' for i in range(len(head))] for j in range(len(result.states)+1)]
        result.transferTable[0] = head
        for j in range(len(result.states)):
            result.transferTable[j+1][0] = result.states[j]
        for i in range(len(self.states)):
            for j in range(len(head)-1):
                if 'ε' in self.transferTable[0]:
                    index = self.transferTable[0].index(head[j+1])
                    if type(self.transferTable[i+1][index]) == int:
                        result.transferTable[i+2][j+1] = aMark[self.states.index(self.transferTable[i+1][index])]
                    elif type(self.transferTable[i+1][index]) == list:
                        exchange = []
                        for value in self.transferTable[i+1][j+1]:
                            exchange += [aMark[self.states.index(value)]]
                        result.transferTable[i+2][j+1] = exchange
                else:
                    if head[j+1] != 'ε':
                        index = self.transferTable[0].index(head[j+1])
                        if type(self.transferTable[i+1][index]) == int:
                            result.transferTable[i+2][j+1] = aMark[self.states.index(self.transferTable[i+1][index])]
                        elif type(self.transferTable[i+1][index]) == list:
                            exchange = []
                            for value in result.transferTable[i+2][j+1]:
                                exchange += [aMark[self.states.index(value)]]
                            result.transferTable[i+2][j+1] = exchange
        result.transferTable[1][head.index('ε')] = [1, 100]
        result.transferTable[len(result.states)-1][head.index('ε')] = [1, 100]
        return result

    def fomalize(self):
        for i in range(len(self.transferTable)):
            for j in range(len(self.transferTable[0])):
                if type(self.transferTable[i][j]) == int:
                    self.transferTable[i][j] = [self.transferTable[i][j]]

    def showTransferTable(self):
        for line in self.transferTable:
            content = ''
            for value in line:
                content += str(value) + '\t'
            print content
